#include <iostream>
#include <UnidirectionLinkedList.hpp>

using namespace std;

class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        // start | first ... last | end
        ListNode *dummy = new ListNode(0, head);
        ListNode *start = dummy;
        ListNode *last = dummy;
        while (true)
        {
            for (int i = 0; i < k; i++)
            {
                last = last->next;
                if (!last)
                {
                    return dummy->next;
                }
            }
            ListNode *first = start->next;
            ListNode *end = last->next;
            last->next = nullptr;
            Reverse(first);
            start->next = last;
            first->next = end;
            // start | last ... first | end
            start = first;
            last = first;
        }
        return dummy->next;
    }

    void Reverse(ListNode *first)
    {
        if (first->next == nullptr)
            return;
        ListNode *pre = first;
        ListNode *cur = first->next;
        pre->next = nullptr;
        while (cur->next != nullptr)
        {
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        cur->next = pre;
    }
};

int main()
{
    cout << "Code25" << endl;
    Solution s;
    ListNode* head = CreateLinkedList(vector<int>{1,2,3,4,5});
    PrintLinkedList(s.reverseKGroup(head, 2));
    return 0;
}